package queue.homework;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 思考：我们能不能将top的复杂度降至O(1)
 * 答案是可能的，我们没必要在每次取出栈顶元素的时候，都把所有的元素再拿出来一边
 * 在整个类中，我们可以使用一个变量，假设就叫做top，来追踪我们记录的栈顶元素：
 *
 * 现在，MyStack2,top方法的时间复杂度变成O（1）了。其他方法的时间复杂度没有变化。
 *
 */
public class MyStack2 {

    private Queue<Integer> q;
    private int top; //追踪记录栈顶元素


    /**
     * Initialize your data structure here.
     * O（1）
     */
    public MyStack2() {
        q = new LinkedList<>();
        top = 0;
    }

    /**
     * 对于一个栈来说，关键是栈顶在哪里。
     * <p>
     * 栈是一端入，同一端出；而队列是一段入，另一端出。如果只给一个队列，我们先假设，入队的一端是栈顶。
     * <p>
     * 一旦这样定义，那么，我们封装的这个MyStack的入栈操作就很简单：直接把元素入队即可
     * O（1）
     *
     * @param x
     */
    public void push(int x) {
        q.add(x);
        top = x;
    }


    /**
     * 而我们的top过程，因为拿出栈顶元素后，top里存放新的栈顶元素，所以，我们也需要维护top，注意下面的注释：
     *
     * @return
     */
    public int pop() {
        //创建另外一个队列q2
        Queue<Integer> q2 = new LinkedList<>();
        //除了最后一个元素，将q中的所有元素放入q2

        while (q.size() > 1) {
            //每从q中取出一个元素，都给top赋值，
            //top最后存储的就是q中除了队尾以外的最后一个元素
            //即新的栈顶元素
            top = q.peek();
            q2.add(q.remove());

        }
        //q中剩下的最后一个元素就是 “栈顶” 元素
        int result = q.remove();
        //此时q2存储整个数据结构存储的所有其他数据，赋值给q
        q = q2;
        //返回栈顶元素
        return result;
    }

    /**
     * 这样以来，top函数就变得非常简单了
     * O(1)
     *
     * @return
     */
    public int top() {
        return top;
    }

    /**
     * O(1)
     *
     * @return
     */
    public boolean empty() {
        return q.isEmpty();
    }

    /**
     * O（1）
     *
     * @return
     */
    public int getSize() {
        return q.size();
    }
}
